package main

func alienOrder(words []string) string {
	g := map[byte][]byte{}
	inDeg := map[byte]int{}
	for _, c := range words[0] {
		inDeg[byte(c)] = 0
	}
next:
	for i := 1; i < len(words); i++ {
		bf, af := words[i-1], words[i]
		for _, c := range af {
			inDeg[byte(c)] += 0
		}
		for j := 0; j < len(bf) && j < len(af); j++ {
			if bf[j] != af[j] {
				g[bf[j]] = append(g[bf[j]], af[j])
				inDeg[af[j]]++
				continue next
			}
		}
		if len(bf) > len(af) {
			return ""
		}
	}

	order := make([]byte, len(inDeg))
	q := order[:0]
	for u, d := range inDeg {
		if d == 0 {
			q = append(q, u)
		}
	}
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		for _, v := range g[u] {
			if inDeg[v]--; inDeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if cap(q) == 0 {
		return string(order)
	}
	return ""
}
